package gold.enterprise;

public class MicroSoftThree {

    public int findK(int[] nums1, int[] nums2, int k) {
        return findKthRecur(nums1, nums2, 0, nums1.length - 1, 0, nums2.length, k);
    }

    public int findKthRecur(int[] nums1, int[] nums2, int start1, int end1, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;

        //保证num1更短吧
        if (len1 > len2) {
            return findKthRecur(nums2, nums1, start2, end2, start1, end1, k);
        }

        if (len1 == 0) return nums2[start2 + k - 1];
        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return findKthRecur(nums1, nums2, start1, end1, j + 1, end2, k - (j - start2 + 1));
        } else {
            return findKthRecur(nums1, nums2, i + 1, end1, start2, end2, k - (i - start1 + 1));
        }
    }


    public static void main(String[] args) {
        int[] arr1 = {1, 2, 3};
        int[] arr2 = {2, 9, 10, 12};

        MicroSoftThree solution = new MicroSoftThree();
        for (int i = 1; i < 8; i++) {
            System.out.println(solution.findK(arr1, arr2, i));
        }

    }

}
